package q1240_tilingRectangle;

public class Solution {
    /*
    经典铺瓷砖，用dp来做
    分别考虑横着切和竖着切以及将中间切出来一块
     */
    public int tilingRectangle(int n, int m) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果是正方形
                if (i == j) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = INF;
                // 1.横切
                for (int k = 1; k < i; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
                // 2.竖切
                for (int k = 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[i][j - k]);
                }

                // 3.横竖切
                for (int p = 1; p <= Math.min(i, j); p++) {
                    for (int k = 1; k <= p; k++) {
                        if (p - k <= 0 || j - p <= 0 || i - p + k <= 0 || j - p - k <= 0) continue;
                        dp[i][j] = Math.min(dp[i][j], dp[p - k][j - p] + dp[i - p + k][j - p - k] + dp[i - p][p + k] + 2);
                    }
                }
            }
        }
        return dp[n][m];
    }
}
